|
: In computer science, a ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as "left", “mid” and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left, mid or right child. Ternary trees are used to implement Ternary search trees and Ternary heaps. ==Definition== * Directed Edge - The link from the parent to the child. * Root - The node with no parents. There is at most one root node in a rooted tree. * Leaf Node - The node which has no children. * Parent Node - Any node connected by a directed edge to its child or children. * Child Node - Any node connected to a parent node by a directed edge. * Depth - Length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero. * Height - Length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero. In the example diagram, the tree has height of 2. * Sibling - Nodes that share the same parent node. - A node p is an ancestor of a node q if it exists on the path from q to the root. The node q is then termed a descendant of p. - A size of a node is the number of descendants it has including itself. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ternary tree」の詳細全文を読む スポンサード リンク
|